package demo2;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Stack;

public class LinkListDemo {

    public Node makeNode() {
        return new Node(1);
    }
    @Getter
    @AllArgsConstructor
    @NoArgsConstructor
    class Result{
        private int size;
        private Node current;

    }
    @NoArgsConstructor
    public class Node {
        public int data;
        public  Node next = null;
        public  Node prev = null;
        public  Node next_next = null;
        private Node head;
        private Node firstHead;
        private Node secondHead;

        public Node(int data) {
            this.data = data;
        }

        // make up the link
        public Node makeUpLinkList(Node head) {
            // the data val is 0 , only placeHolder
            return head.add(new Node(2)).add(new Node(3)).add(new Node(1)).add(new Node(3)).add(new Node(1)).add(new Node(5))
                    .add(new Node(6)).add(new Node(3)).add(new Node(0));

        }

        public Node add(Node node) {
            this.next = node;
            return node;
        }

        /**
         * foreach the list ,then setting the next-next point .
         */
        public void makeUpLinkListForNextNext(Node node) {
            while (node.next != null) {
                node.next_next = node.next.next;
                node = node.next;
            }
        }

        public Node lastKNodeWithRecursionAndMakeNode() {
            Node node = this;
            makeUpLinkList(node);
            makeUpLinkListForNextNext(node);
            printNodeVal(node);
            return lastKNodeWithRecursion(node, 10 - 5 + 1); // 5
        }

        //last          5 4
        //  1,2,3,1,3,1,5,6,3,0   => when know the array length=10  get the val is 1
        public Node lastKNodeWithRecursion(Node node, int count) {
            // get the k-1 ~ N
            if (node.next == null) return null;
            if (count == 0) {
                assert node.next_next.data == 3;
                assert node.data == 5;
                return node;
            }
            node = node.next;
            return lastKNodeWithRecursion(node, count - 1);
        }

        // how do this ? when only access the dest node?
        public void removeCenterNode() {
            Node node = this;
            // 1,2,3,1,3,1,5,6,3,0   , remove the 1 then the  location is four in order asc
            makeUpLinkList(node);
            printNodeVal(this);
            int i = 1;
            while (node != null) {
                if (i++ == 3) {
                    assert node.next.data == 1;
                    node.next = node.next.next;
                    break;
                }
                node = node.next;
            }
            // assert res is : 1,2,3,3,1,5,6,3,0,
            printNodeVal(this);
        }

        public void cutUpLinkList(int x) {
            Node node = new Node(3);
            // 1,3,5,8,5,10,2,1  when x=5
            // 1,3,2,1   |  5,8,5,10,[2,1]
            node.add(new Node(5)).add(new Node(8)).add(new Node(5)).add(new Node(10)).add(new Node(2))
                    .add(new Node(1));
            printNodeVal(node);

            Node low = null;
            Node lowhead = null;
            Node high = null;
            Node highHead = null;
            Node newNode = null;
            Node newNodeHead = null;
            // foreach clip the each list .
            int lowCount = 0;
            int highCount = 0;
            while (node != null) {
                if (node.data < x) {
                    if (low == null) {
                        low = new Node(node.data); // init
                        lowhead = low;
                    } else {
                        low.next = node;
                        low = low.next;
                    }
                    lowCount++;
                }
                if (node.data >= x) {
                    if (high == null) {
                        high = new Node(node.data);
                        highHead = high;
                    } else {
                        high.next = node;
                        high = high.next;
                    }
                    highCount++;
                }
                node = node.next;
            }


            // merge the linklist
            low = lowhead;
            int lowIncrement = 0;
            while (low != null) {
                //
                if (lowIncrement++ == lowCount) {
                    newNode.next = null;
                    break;
                }
                if (newNode == null) {
                    newNode = new Node(low.data);
                    newNodeHead = newNode;
                } else {
                    newNode.next = low;
                    newNode = newNode.next;
                }
                low = low.next;
            }
            int highIncrement = 0;
            high = highHead;

            while (high != null) {
                if (highIncrement++ == highCount) {
                    // cut up the link.
                    newNode.next = null;
                    break;
                }
                if (newNode == null) {
                    newNode = new Node(high.data);
                    newNode = newNodeHead;
                } else {
                    newNode.next = high;
                    newNode = newNode.next;
                }
                high = high.next;
            }
            // update the head
            printNodeVal(newNodeHead);

        }

        private int numberCharToInt(char x) {
            int y = (int) x - 48;
            return y;
        }

        public void makeUpLinkForSumLinkListWithRecursionInOrderAsc() {
            //
            Node first = new Node(6);
            Node firstHead = first;
            first.add(new Node(1)).add(new Node(7));

            Node second = new Node(2);
            Node secondHead = second;

            second.add(new Node(9)).add(new Node(5));
            // if dont know the  lenth of linklist,the linklist in order desc
            int sum1 = sumLinkListWithRecursionInOrderAsc(firstHead, 3, 0);
            int sum2 = sumLinkListWithRecursionInOrderAsc(secondHead, 3, 0);
            int sum = sum1 + sum2; // 912
            char[] chars = ((Integer) sum).toString().toCharArray();
            // make up the linklist
            Node add = new Node(numberCharToInt(chars[0]));
            this.head = add;
            add.add(new Node(numberCharToInt(chars[1]))).add(new Node(numberCharToInt(chars[2])));

            printNodeVal(this.head);

        }

        public void makeUpLinkForSumLinkListWithRecursion() {
            // (7,1,6) + (5,9,2) => (2,1,9)
            Node first = new Node(7);
            Node firstHead = first;
            first.add(new Node(1)).add(new Node(6));

            Node second = new Node(5);
            Node secondHead = second;

            second.add(new Node(9)).add(new Node(2));
            // if dont know the  lenth of linklist,the linklist in order desc
            int sum1 = sumLinkListWithRecursion(firstHead, 0, 0);
            int sum2 = sumLinkListWithRecursion(secondHead, 0, 0);
            int sum = sum1 + sum2; // 912
            char[] chars = ((Integer) sum).toString().toCharArray();
            // make up the linklist
            Node add = new Node(numberCharToInt(chars[0]));
            this.head = add;
            add.add(new Node(numberCharToInt(chars[1]))).add(new Node(numberCharToInt(chars[2])));

            printNodeVal(this.head);

        }

        /**
         * 617,need to know the length of linklist
         */
        public int sumLinkListWithRecursionInOrderAsc(Node node, int count, int sum) {
            if (node == null) {
                return sum;
            }
            //   10^2 ,10^1
            int pow = (int) Math.pow(10d, (double) (count - 1));
            sum += node.data * pow;
            return sumLinkListWithRecursionInOrderAsc(node.next, count - 1, sum);

        }

        /**
         * 716 =>
         */
        public int sumLinkListWithRecursion(Node node, int count, int sum) {
            if (node == null) {
                return sum;
            }
            int pow = (int) Math.pow(10d, (double) (count));
            sum += node.data * pow;
            return sumLinkListWithRecursion(node.next, count + 1, sum);
        }
        // tacocat
        // 12344321  yes
        // 12344325  no
        // 00000000

        /**
         * make the linklist roll ,
         * 1. use stack , easy
         */
        public boolean checkLinkListForIsPalindrome() {
            Node node = new Node(1);
            this.firstHead = node;
//  yes          node.add(new Node(2)).add(new Node(3)).add(new Node(4)).add(new Node(3)).add(new Node(2)).add(new Node(1));
            // no
            node.add(new Node(2)).add(new Node(3)).add(new Node(4)).add(new Node(3)).add(new Node(2)).add(new Node(5));

            Stack stack = new Stack<Node>();
            ArrayList list = new ArrayList<Integer>();

            while (node != null) {
                stack.push(node.data);
                list.add(node.data);
                node = node.next;
            }
            int i = 0;
            while (!stack.empty()) {
                Integer pop = (Integer) stack.pop();
                if (pop == list.get(i++)) {
                } else {
                    return false;
                }
            }
            return true;
        }
    /**
     * 123789 10  size=7
     * 05789 10   size=5
     *
     * 1 2 3 4 5 6  size=6
     *  4 5 6  size=5
     *  /**
     *              * answer 1:
     *              * while {
     *              *     while{
     *              *          if(A=B) then have interact
     *              *     }
     *              * }
     *              * answer 2:
     *              *   use hashMap.put()
     *              *  O(n^2)
     *              *  answer 3:  the very efficient!!!
     *              *   O(A+B) + 空间 O(1)
     *              *
     *              */
        public Node adjustInteract(){
            Node node = new Node(7);
            Node node8 = new Node(8);
            Node node9 = new Node(9);
            Node node10 = new Node(10);

            Node first=new Node(1);
            this.firstHead=first;
            first.add(new Node(2)).add(new Node(3)).add(node).add(node8).add(node9).add(node10);

            Node second = new Node(0);
            this.secondHead=second;
            second.add(new Node(5)).add(node).add(node8).add(node9).add(node10);

            assert this.firstHead!=null;
            assert this.secondHead!=null;
            return adjust(firstHead,secondHead);
        }
        private Node adjust(Node firstHead,Node secondHead){
            Node tail1 = getTailNode(firstHead);
            Node tail2 = getTailNode(secondHead);
            if(tail1!=tail2){
                return null;
            }
            Result result1 = makeUpNewResult(firstHead);
            Result result2 = makeUpNewResult(secondHead);

            // longer and shorter
            Node longer= result1.getSize()>result2.getSize()?result1.getCurrent():result2.getCurrent();
            Node shorter= result1.getSize()>result2.getSize()?result2.getCurrent():result1.getCurrent();

            Node clipLonger = clip(longer, Math.abs(result1.size - result2.size));
 // get  same ref
            while(clipLonger!=shorter){
                clipLonger = clipLonger.next;
                shorter=shorter.next;
            }
            return clipLonger;
        }
        private Node clip(Node node,int count){

            while (node!=null){
                if(count--==0){
                    break;
                }
                node=node.next;
            }
            return node;
        }
        private Node getTailNode(Node node){

            while(node.next!=null){
                node=node.next;
            }
            return node;
        }
        private Result makeUpNewResult(Node node){
            Node head = node;
            int count=1;
            while(node!=null){
                count++;
                node=node.next;
            }
            // get the head node
            return new Result(count,head);
        }

        /**
         * 有环 4->4
         * 1 2 3 4
         * N 2N
         * 2 3
         * 3 4
         * 4 4                    4
         *
         * 有环 4->3
         * 1 2 3 4
         * N 2N
         * 2 3
         * 3 3                    3
         * 1 3 ->
         * 2 4
         * 3 3
         *
         *
         * 有环 4->2
         * 1 2 3 4
         * N 2N
         * 2 3
         * 3 2
         * 4 4                    4      slow to head , each run one steps
         * 1 4 ->
         * 2 2
         *
         *
         * 有环 4->1
         * 1 2 3 4 1
         * N 2N
         * 2 3
         * 3 1
         * 4 3
         * 1 1              ->1
         *
         *
         */
        // if the slow go to the end , slow and faster could not meeting!
        public Node loopCheckForLinkListAndGetMeetingPoint(){
            Node first =new Node(1);
            Node node = new Node(2);

            this.firstHead=first;

            first.add(node).add(new Node(3)).add(new Node(4)).add(node);
            //  A(faster) one times faster than B
            Node faster =  makeUpTheFastPoint(firstHead);
            // todo you can check the linklist whether loop . when is loop .then use below
            // get the begging of loop;
            first=this.firstHead;
            first=first.next;
            faster=faster.next.next;

            // iterate   in two point
            while (first !=faster ){
                first = first.next;
                faster=faster.next.next;
            }
            first=this.firstHead;

            while (first!=faster) {
                first=first.next;
                faster=faster.next;
            }
            return faster;

        }
        private Node makeUpTheFastPoint(Node firstHead){
           return firstHead;
        }

        /**
         * todo
         */
        public void removeDuplicateWithDoublePoint() {
            Node node = this;
            HashSet<Integer> set = new HashSet<Integer>();
            makeUpLinkList(node);
            printNodeVal(node);
            System.out.println("=======================================");
            set.add(node.data);
            new Node(1);


        }

        /**
         * use the double-list
         */
        public void removeDuplicate() {
            // use buffer that is hashSet
            Node node = this;
            HashSet<Integer> set = new HashSet<Integer>();
            // or only just add node to  here.
            makeUpLinkList(node);
            printNodeVal(node);
            System.out.println("=======================================");
            set.add(node.data);
            Node tmp = this;
            Node lastNode = this;

            while (node.next != null) {
                boolean add = set.add(node.next.data); // 1,2,3,1,3,1,5,6,3,4,9
                if (!add) {
                    tmp = node;
                    a:
                    while (node.next.next != null) {
                        boolean add1 = set.add(node.next.next.data);
                        if (!add1) {
                            node = node.next;
                            continue;
                        } // duplicate 跳过链子
                        if (add1) { // true => not duplicate
                            tmp.next = node.next.next; // 1,2,3,3
                            break a;
                        }
                    }
                }
                lastNode = node;
                node = node.next;
            }
            lastNode.next = null;

            // get head
            printNodeVal(this);

        }

        private void printNodeVal(Node node) {
            StringBuilder sb = new StringBuilder(1024);
            sb.append(node.data).append(",");
            while (node.next != null) {
                sb.append(node.next.data).append(",");
                node = node.next;
            }
            System.out.println(sb.toString());
        }
    }

}
